<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉树</title>
</head>
<body>
    <script type="text/javascript">
        function BinaryTree() {
        // 内部方法————————————————————————————————————————————————————-
            // 节点对象
            let Node = function(key) {
                this.key = key
                this.left = null
                this.right = null
            }
            // 根节点
            let root = null;
            // 节点插入
            function insertNode(parent,children) {
                if( parent.key > children.key) {
                    if(parent.left === null) {
                        parent.left = children
                    }else{
                        insertNode(parent.left, children)
                    }  
                }else{
                    if(parent.right === null) {
                        parent.right = children
                    }else{
                        insertNode(parent.right, children)
                    }
                }
            }
        // 实例方法——————————————————————————————————————————————————————
            // 根据传入数据构造二叉树
            this.insert = function(key) {
                let newNode = new Node(key)
                if(root === null) {
                    root = newNode
                }else{
                    insertNode(root, newNode)
                }
            }
            // 中序遍历二叉树 (从小到大排序)
            let inOrderTraverseNode = function(node, callback) {
                if(node !== null) {
                    inOrderTraverseNode(node.left, callback)
                    callback(node.key)
                    inOrderTraverseNode(node.right, callback)
                }else{
                    return false
                }
            }
            this.inOrderTraverse = function(callback) {
                inOrderTraverseNode(root, callback)
            }
            // 前序遍历二叉树 
            let preOrderTraverseNode = function(node, callback) {
                if(node !== null) {
                    callback(node.key)
                    preOrderTraverseNode(node.left, callback)
                    preOrderTraverseNode(node.right, callback)
                }
            }
            this.preOrderTraverse = function(callback) {
                preOrderTraverseNode(root, callback)
            }
            // 后序遍历二叉树
            let postOrderTraverseNode = function(node, callback) {
                if(node !== null) {
                    postOrderTraverseNode(node.left, callback)
                    postOrderTraverseNode(node.right, callback)
                    callback(node.key)
                }
            }
            this.postOrderTraverse = function(callback) {
                postOrderTraverseNode(root, callback)
            }
            // 查找二叉树最小值
            let minTraverseNode = function(node) {
                if(node !== null) {
                    while(node && node.left !== null) {
                        node = node.left
                    }
                }
                return node
            }
            this.minNode = function() {
                let min =  minTraverseNode(root)
                return min.key
            }
            // 查找二叉树最大值
            let maxTraverseNode = function(node) {
                if(node !== null) {
                    while(node && node.right !== null) {
                        node = node.right
                    }
                }
                return node
            }
            this.maxNode = function() {
                let max =  maxTraverseNode(root)
                return max.key
            }
            // 查找指定值
            let findNode = function(node, key) {
                if(node !== null) {
                    if(node.key > key) {
                        findNode(node.left, key)
                    }else if(node.key === key){
                        console.log('存在该节点！') 
                    }else{
                        findNode(node.right, key)
                    } 
                }
            }
            this.find = function(key) {
                findNode(root, key)
            }
            // 删除节点
            let removeNode = function(node, key) {
                if(node !== null) {
                    // 1.查找
                    if(node.key > key) {
                        node.left = removeNode(node.left, key)
                        return node
                    }else if(node.key === key){
                        // 2.删除
                        if( node.left === null && node.right === null ) {
                            // 删除叶子节点
                            node = null
                            return node
                        }else if( node.right === null ){
                            // 删除单分支节点
                            node = node.left
                            return node
                        }else if( node.left === null ){
                            node = node.right
                            return node
                        }else{
                            // 删除双分支节点
                            let chgNode = minTraverseNode(node.right)
                            node.key = chgNode.key
                            node.right = removeNode(node.right, chgNode.key)
                            return node
                        }
                    }else{
                        node.right = removeNode(node.right, key)
                        return node
                    } 
                }
            }
            this.remove = function(key) {
                removeNode(root, key)
            }
        }
        // 实例数组
        let arr = [5, 9, 1, 0, 4, 2, 10, 3, -1, 6, 8]
        // 实例化二叉树对象
        let binaryTree = new BinaryTree()
        // 构建二叉树
        arr.forEach( key => {
            binaryTree.insert(key)
        });
        function callback(res) {
                console.log(res)
        }
        // binaryTree.inOrderTraverse(callback)
        // binaryTree.preOrderTraverse(callback)
        // binaryTree.postOrderTraverse(callback)
        // let min = binaryTree.minNode()
        // console.log(min)
        // let max = binaryTree.maxNode()
        // console.log(max)
        // binaryTree.find(2)
        binaryTree.remove(4)
        // binaryTree.remove(3)
        binaryTree.inOrderTraverse(callback)
    </script>
</body>
</html>